package jjn.round1;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author Jjn
 * @since 2022/11/4 20:21
 */
public class LeetCode215_KthLargestElementInArray {
    /**
     * 要求O(n)时间复杂度，也就是不能排序
     *
     * @param nums nums
     * @param k    k
     * @return kth largest num
     */
    public int findKthLargest(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>(Comparator.reverseOrder());
        for (int num : nums) {
            Integer integer = map.getOrDefault(num, 0);
            integer++;
            map.put(num, integer);
        }
        int total = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            total += value;
            if (total >= k) {
                return key;
            }
        }
        return -1;
    }
}
